package leetcode.dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
 *
 * 示例1:
 *
 *  输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 *  输出：true
 * 示例2:
 *
 *  输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 *  输出 true
 * 提示：
 *
 * 节点数量n在[0, 1e5]范围内。
 * 节点编号大于等于 0 小于 n。
 * 图中可能存在自环和平行边。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/route-between-nodes-lcci
 */
public class 有向图节点通路 {

    private static boolean dfs(List<Integer>[] l, boolean[] flag, int start, int target){
        // 该节点已被遍历 或 无子节点 返回false
        if (flag[start] || l[start] == null){ return false; }
        // 找到目标节点
        if (start == target){ return true; }
        // 遍历子节点
        for (int i : l[start]){
            // 标记
            flag[start] = true;
            // 到达目标节点则快速结束递归
            if (dfs(l, flag, i, target)){ return true; }
            // 回溯
            flag[start] = false;
        }
        return false;
    }
    public static boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        List<Integer>[] l = new List[n];
        // 访问记录
        boolean[] flag = new boolean[n];
        for (int[] i : graph){
            l[i[0]] = l[i[0]]==null ? new ArrayList() : l[i[0]];
            l[i[0]].add(i[1]);
        }
        return dfs(l, flag, start, target);
    }

    public static void main(String[] args){
        int[][] graph = new int[][]{{0, 1}, {0, 2}, {0, 4}, {0, 4}, {0, 1}, {1, 3}, {1, 4}, {1, 3}, {2, 3}, {3, 4}};
        System.out.println(findWhetherExistsPath(5, graph, 1, 2));
    }
}
